//
// Description: 75. 颜色分类
// Created by Loading on 2022/4/5.
//

#include <bits/stdc++.h>

using namespace std;

void sortColors(vector<int> &nums) {
    int n = nums.size();

    int ptr0 = 0, ptr1 = 0;
    /* 双指针，一轮扫描 */
    for (int i = 0; i < n; ++i) {
        if (nums[i] == 1) {
            swap(nums[ptr1], nums[i]);
            ++ptr1;
        } else if (nums[i] == 0) {
            swap(nums[ptr0], nums[i]);
            // ptr0 < ptr1 时，交换到后边的是1，需要再次和ptr1交换回来
            if (ptr0 < ptr1) {
                swap(nums[ptr1], nums[i]);
            }
            ++ptr0;
            ++ptr1;
        }
    }
}

int main() {
    vector<int> nums{0, 0, 2, 0, 1, 0, 1, 2, 1, 2, 0};
    sortColors(nums);
    for (auto x : nums) {
        cout << x << ' ';
    }

    return 0;
}